//
//  main.swift
//  01-冒泡排序
//
//  Created by XFB on 2020/4/3.
//  Copyright © 2020 XFB. All rights reserved.
//

import Foundation

/**
 冒泡排序：不稳定排序 最好不要写 ... 但是是原地排序
 原地排序：不依赖额外的资源或者依赖少数的额外资源（针对空间复杂度），仅依靠输出来覆盖输入
 空间复杂度为O(1)的都可以认为是原地算法
 
 执行流程
 1、从头开始比较每一对相邻元素，如果第0个比第一个大，就交换位置
    执行完一轮后，最末尾那个元素就是最大元素
 2、忽略第一轮找到最大元素，重复执行第一步操作
 
 
 优化：如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
 
 空间复杂度O(1) 原地算法
 不依赖额外的资源或者依赖少数的额外资源，仅l依靠输出覆盖输入
 */

// 冒泡排序
func BubbleSorted(_ nums:[Int]) {
    
    var array = nums
    if array.count == 0 {
        return
    }
    let count = array.count
    // 遍历的次数
    for i in 0 ..< count-1 {
        // 遍历一次，最后一个数字最大不需要再次遍历，需要减去i
        for j in 0 ..< count-1-i {
            // 如果前一个元素 比 后一个元素大，交换位置
            if array[j] > array[j+1] {
                let temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
//    print(array)
}


// 冒泡排序 --- 优化版本1 增加标志位
func BubbleSorted1(_ nums:[Int]) {
    
    var array = nums
    if array.count == 0 {
        return
    }
    let count = array.count
//    print("开始交换前：\(array)")
    for i in 0 ..< count-1 {
        var flag = true
        for j in 0 ..< count-1-i {
            if array[j] > array[j + 1] {
                let temp = array[j]
                array[j] = array[j + 1]
                array[j + 1] = temp
                // 发生交换，标志位为false
                flag = false
            }
//            print("第 \(i+1) 遍的第 \(j+1) 次交换：\(array)");
        }
//        print("第 \(i+1) 遍最终结果：\(array)");

        // 如果没有交换，就已经是有序的
        if flag == true {
            break
        }
    }
//    print(array)
}

// 数组尾部局部有序，记录标志位，减少比较次数
func BubbleSorted2(_ nums:[Int]) {
    var array = nums
    if array.count == 0 {
        return
    }
    
    let count = array.count
    for var i in 0 ..< count-1 {
        var sortedIndex = 0
        for j in 0 ..< count-1-i {
            if array[j] > array[j + 1] {
                let temp = array[j];
                array[j] = array[j + 1]
                array[j + 1] = temp
                sortedIndex = j;
            }
        }
        i = sortedIndex + 1
    }
//    print(array)
}

func selectionSorted(_ nums: [Int]) {
    var array = nums
//    print(array)

    // 扫描多少次
    for i in 0 ..< array.count - 1  {
        // 默认第0个位置是最小值
        var minIndex = i
        for j in i ..< array.count {
            if array[minIndex] > array[j] {
                minIndex = j
            }
        }
//        array.swapAt(i, minIndex)
        let temp = array[minIndex]
        array[minIndex] = array[i]
        array[i] = temp
    }
    
    // 打印是否已经排好序
//    print(isAscOrder(array: array))
}


// 生成随机数
//let nums = RandomArray(min: 1, max: 10, length: 5)
// orderCount 排好序的个数
//let nums = tailOrderRandomArray(min: 1, max: 20000, orderCount: 15000)
// 升序
let nums = ascOrderRandomArray(min: 3, max: 10000)
// 降序
//let nums = descOrderRandomArray(min: 3, max: 10)
//print(nums)
let nums1 = nums
let nums2 = nums
let nums3 = nums
let nums4 = nums

//let nums5 = tailOrderRandomArray(min: 1, max: 1000, orderCount: 50)
//print(nums5)

// 冒泡排序
//let time = executeTime {
//    BubbleSorted(nums)
//}
//print("冒泡排序耗时：\(time)秒")
//
//// 冒泡排序 - 优化1
//let time1 = executeTime {
//    BubbleSorted1(nums1)
//}
//print("冒泡排序优化1后耗时：\(time1)秒")
//
// 冒泡排序 - 优化2
let time2 = executeTime {
    BubbleSorted2(nums2)
}
print("冒泡排序优化2后耗时：\(time2)秒")
//
// 冒泡排序 - 优化2
//let time4 = executeTime {
//    selectionSorted(nums4)
//}
//print("选择排序耗时：\(time4)秒")


//let bubbleSort = BubbleSort.init(array: nums)
//let time = executeTime {
//    bubbleSort.sort()
//}
//print("冒泡排序耗时：\(time)秒")
//print(isAscOrder(array: bubbleSort.sortArray))

//let bubbleSort1 = BubbleSort.init(array: nums1)
//let time1 = executeTime {
//    bubbleSort1.sort1()
//}
//print("冒泡排序耗时：\(time1)秒")
//print(isAscOrder(array: bubbleSort1.sortArray))

//let bubbleSort2 = BubbleSort.init(array: nums2)
//let time2 = executeTime {
//    bubbleSort2.sort2()
//}
//print("冒泡排序耗时：\(time2)秒")
//print(isAscOrder(array: bubbleSort2.sortArray))




//// 针对已经排好序的
//func BubbleSorted3(_ nums:[Int]) {
//    // 此情况会在一开始就是排序好的，速度最快
//    // 情况最差的是降序的数组，
//    var array = nums
//    if array.count == 0 {
//        return
//    }
//    let count = array.count
//    for end in 0 ..< count-1 {
//        var sorted = true
//        for start in 0 ..< count-1-end {
//            if array[start] > array[start + 1] {
//                array.swapAt(start, start + 1)
//                sorted = false
//            }
//        }
//        if sorted == true {
//            break
//        }
//    }
////    print(array)
//}

//// 冒泡排序 - 优化3
//let time3 = executeTime {
//    BubbleSorted3(nums3)
//}
//print("冒泡排序优化3后耗时：\(time3)秒")

